package com.zhanghp.class06;

import com.zhanghp.refer.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * <h1>二叉树路径总和Ⅱ</h1>
 * <p>给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。叶子节点 是指没有子节点的节点。</p>
 * <a href = "https://leetcode.cn/problems/path-sum-ii">leetcode</a>
 *
 * @author zhp
 * @since 2024/1/23 18:03
 */
public class Code05_PathSumII {

    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        List<List<Integer>> ans = new ArrayList<>();
        if (root == null) {
            return ans;
        }
        process(root, 0, sum, new ArrayList<>(), ans);
        return ans;
    }

    public void process(TreeNode x, int preSum, int targetSum, List<Integer> path, List<List<Integer>> ans) {
        // 左右树都为空，判断累加和是否相等指定的和
        if (x.left == null && x.right == null) {
            if (targetSum == preSum + x.val) {
                // 加入当前path
                path.add(x.val);
                // 拷贝一份，因为是引用地址，所以拷贝新的list放进结果集里
                ans.add(copy(path));
                // 由于此结束完，所以减掉当前节点的路径值，方便上一层根节点对它下个节点遍历
                path.remove(path.size() - 1);
            }
            return;
        }
        // 累加和
        preSum += x.val;
        // 路径加入当前路径值
        path.add(x.val);
        // 左树判断
        if (x.left != null) {
            process(x.left, preSum, targetSum, path, ans);
        }
        // 右树判断
        if (x.right != null) {
            process(x.right, preSum, targetSum, path, ans);
        }
        // 移除当前路径
        path.remove(path.size() - 1);
    }

    public List<Integer> copy(List<Integer> list) {
        List<Integer> ans = new ArrayList<>();
        if (list == null || list.isEmpty()) {
            return ans;
        }
        ans.addAll(list);
        return ans;
    }

}
